A known multiprocessor system (Wong, F. S. and ITO, M. R.: A Loop-Structured Switching Network, IEEE Transactions on Computers, C-33, 5, pp 450-455; 1984) is built up of 64 standard microprocessor modules in which the interprocessor exchange is realized by a cyclic four-stage interconnection network, where each stage comprises eight communication nodes and to each node there are connected two processor elements.
The communication connections between the first and the second stage are distributed in four groups, and each group comprises two adjacent communication nodes of the first stage and two adjacent communication nodes of the second stage.
Within one group, the first output of the first communication node of the first stage is connected to the first input of the first communication node of the second stage, the second output of the first communication node of the first stage is connected to the first input of the first communication node of the second stage, the second output of the first communication node of the first stage is connected to the first input of the second communication node of the second stage, the first output of the second communication node of the first stage is connected to the second input of the first communication node of the second stage, the second output of the second communication node of the first stage is connected to the second input of the second communication node of the second stage.
The communication connections between the second and the third stage are separated in two groups, and each group comprises four adjacent communication nodes of the second stage and four adjacent communication nodes of the third stage. Within each group, the first output of the first communication node of the second stage is connected to the first input of the first communication node of the third stage, the second output of the first communication node of the second stage is connected to the first input of the third communication node of the third stage, the first output of the second communication node of the second stage is connected to the first input of the second communication node of the third stage, the second output of the second communication node of the second stage is connected to the first input of the fourth communication node of the third stage.
The first output of the third communication node of the second stage is connected to the second input of the first communication node of third stage, the second output of the third communication node of the second stage is connected to the second input of the third communication node of the third stage.
The first output of the fourth communication node of the second stage within one group is connected to the second input of the second communication node of the third stage, the second output of the fourth communication node of the second stage is connected to the second input of the fourth communication node of the third stage.
The outputs of the communication nodes of the third stage are distributed in two groups, and each group comprises the outputs of four adjacent communication nodes of the third stage.
The inputs of the communication nodes of the fourth stage are distributed in two groups, and each group comprises the inputs of four adjacent communication nodes of the fourth stage.
The first outputs of the communication nodes of the third stage of the first group are connected respectively to the first inputs of the communication nodes of the fourth stage of the first group.
The second outputs of the communication nodes of the third stage of the first group are connected respectively to the first inputs of the communications nodes of the fourth stage of the second group.
The first outputs of the communication nodes of the second group of the third stage are connected respectively to the second inputs of the communication nodes of the first group of the fourth stage.
The second outputs of the communication nodes of the second group of the third stage are connected respectively to the second inputs of the communication nodes of the second group of the fourth stage.
The communication nodes of the first stage are distributed in two groups, and each group comprises four adjacent communication nodes. The first outputs of the communication nodes of the fourth stage are connected respectively to the inputs of the communication nodes of the first group in a first stage, the second outputs of the communication nodes of the fourth stage are connected respectively to the inputs of the communication nodes of the second group in the first stage.
Each communication node comprises six input buffers which are distributed uniformly in two groups, and the output of each of the two input ports is connected to the inputs of the three buffers of one group, as well as four intermediate ports, distributed uniformly in two groups.
The outputs of the first buffers of both groups are connected respectively to the first and the second output port. The outputs of the second buffers of both groups are connected to the input of the first intermediate port of the first group and the input of the second intermediate port of the second group. The outputs of the third buffers of the first and the second group are connected in parallel to the inputs of the second intermediate port of the first group and the first intermediate port of the second group.
The outputs of both intermediate ports of the first group are connected to the input of the first output port; the outputs of both intermediate ports of the second group are connected to the input of the second output port.
The communication between the processor elements is realized by the exchange of messages by means of commutation of packets.
The regulation of the traffic in the interconnection network is based on priority discipline in three levels, and when the packets pass via the communication connections between the fourth and the first stage their priority is increased by one. The first input buffers of the first and second group comprise packets with priority 2, the second input buffers of both groups comprise packets with priority 1, the third input buffers of both groups comprise packets with zero priority.
In the routine of the packet from the source to the destination, the packet is commutated through the communication nodes in the different stages, and the following operations are realized.
(a) when the packet passes through the input port of the communication node, it is loaded in one of the three input buffers depending on its priority;
(b) the packets with priority 2 are commutated by the first input buffer of each group directly to the respective output port;
(c) the packets with priority 0 or 1 are commutated first by the input buffers to the respective intermediate ports, and then to the respective output port;
(d) in the output port there is effected a comparison of the destination address of the packet with the address of the adjacent processor module; and
(e) in the case of coincidence of addresses, the packet is transmitted to the adjacent processor module, or else it is routed to the next-following stage of the interconnection network.
A drawback of this multiprocessor system lies in the complex hardware at the communication nodes, the low adaptibility for implementation in VLSI sysems, the complex priority discipline of the packets in the regulation of the traffic in the network, the low coefficient of hardware utilization in the interconnection network, the low reliability, the lack of a possibility for fault-tolerance and modular expansion of the system.